package sol.leetcode;

import java.util.Arrays;

/**
 * Coin Change
 */
public class Issue322 {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;

        int row = coins.length;
        int col = amount;
        int T[][] = new int[row][col];

        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {

                int pre = j - coins[i];
                int a = i == 0 ? -1 : T[i - 1][j];//上一行同一位置
                int b = pre < 0 ? -1 : T[i][pre];//使用当前行的硬币

                if (j + 1 == coins[i])
                    T[i][j] = 1;
                else {
                    if (a == -1 && b == -1)
                        T[i][j] = -1;
                    else if (a == -1)
                        T[i][j] = b + 1;
                    else if (b == -1)
                        T[i][j] = a;
                    else
                        T[i][j] = Math.min(a, b + 1);
                }
            }
        }

        for (int k = 0; k < row; ++k)
            System.out.println(Arrays.toString(T[k]));

        return T[row - 1][col - 1];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        Issue322 sol = new Issue322();
        System.out.println(sol.coinChange(coins, amount));
    }
}
